package com.leo.basic.chapter06.unionFindSet;

/**
 * 简单的数组并查集
 *      通过数组来维护区域是否连通，相同区域id的数据连通
 *      find时间复杂度为O(1)
 *      Union时间复杂度为O(n)
 * @author xuexiaolei
 * @version 2017年12月13日
 */
public class UFS01 {
    //用一个数组来表示节点的连通性，有相同id内容的节点是连通的
    private int[] mIds;
    //节点个数
    private int mcount;

    /**
     * 初始化状态，并设置每个节点互不连通
     * @param capcity
     */
    public UFS01(int capcity){
        mIds = new int[capcity];
        mcount = capcity;
        for (int i = 0; i < capcity; i++) {
            mIds[i] = i;//各自节点的id都不一样
        }
    }

    /**
     * 返回当前节点的连通id
     * @param p
     * @return
     */
    public int find(int p){
        if (p<0 || p>=mcount){
            throw new RuntimeException("越界喽");
        }
        return mIds[p];
    }

    /**
     * 判断a，b节点是否连通
     * @param a
     * @param b
     * @return
     */
    public boolean isConnect(int a, int b){
        return find(a)==find(b);
    }

    /**
     * 连通a，b节点
     *      联合的整体思路:
     *          要么把a索引在mIds中的状态变成b的，
     *          要么把b索引在mIds中的状态变成a的
     * @param a
     * @param b
     */
    public void union(int a, int b){
        int aId = find(a);
        int bId = find(b);

        //如果已经连通，就不管了
        if (aId == bId){
            return;
        }

        //将bId的全部变成aId,需要将每个节点的id都变过来的
        for (int i = 0; i < mIds.length; i++) {
            if (mIds[i] == bId){
                mIds[i] = aId;
            }
        }
    }
}
